package com.javaDemo.ti;

/**
 * @ClassName: Heweisumdezuhe
 * @Auther: csy https://blog.csdn.net/qq_19446965/article/details/81775702
 * @Date: 2021/7/23 15:30
 * @Description:
 */
public class Heweisumdezuhe {
    // 判断是否有和为n的组合，动规法，O(n^2)
    public static boolean findSum(int[] a, int n) {
        boolean[] dp = new boolean[n + 1];
        for (int i = 0; i < a.length; i++) {
            if (a[i] > n) {
                continue;
            }
            for (int j = n; j >= a[i]; j--) {
                if (dp[j - a[i]]) {
                    dp[j] = true;
                }
            }
            dp[a[i]] = true;
            if (dp[n]) {
                return true;
            }
        }
        return false;
    }

    // 有几种和为n的组合，动规法，O(n^2)
    public static int findSum2(int[] a, int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > n) {
                continue;
            }
            for (int j = n; j >= a[i]; j--) {
                if (dp[j - a[i]] > 0) {
                    dp[j] += dp[j - a[i]];
                }
            }
            if (dp[a[i]] == 0) {
                dp[a[i]] = 1;
            }
        }
        return dp[n];
    }
}
